package com.king.alg;

import com.king.pojo.Point;
import com.king.pojo.TurnFitExtendResult;

import java.util.*;

/**
 * 计算拐点索引，计算拟合点列，计算外扩点列
 * <p>
 * 原始点列：由移动设备获得的GPS点列，是没有经过任何算法处理过的有序的经纬度列表
 * 坐标点列：将原始点列转化为平面上的点列，经过原点，并且放大来提高精度
 * 等距点列：将坐标点列经过等距取点算法后得到的点列，其中索引相邻的两个点之间的
 * 拐点：在等距点列中选取的拐点
 */
public class TurnFitExtendAlgorithms {

    /**
     * 在对坐标点列等距取点时，根据给定的最小距离和开始索引得到下一个点的索引，给定其中任意一个点的索引，即开始索引，
     * 再给定一个距离，即最小距离，此算法会从开始索引的下一个索引依次遍历，如果与开始点的距离大于最小距离则返回此点的索引
     *
     * @param coordinatePointList 坐标点列
     * @param distance            最小距离
     * @param beginIndex          开始索引
     * @return 下一个点的索引
     */
    private static int getNextPointIndexByDistance(List<Point> coordinatePointList, double distance, int beginIndex) {
        if (beginIndex >= coordinatePointList.size() - 1) {
            return coordinatePointList.size() - 1;
        }

        for (int i = beginIndex + 1; i < coordinatePointList.size(); i++) {
            double dis = GeometryAlgorithms.norm(coordinatePointList.get(beginIndex), coordinatePointList.get(i));
            if (dis >= distance) {
                return i;
            }
        }

        return beginIndex;
    }

    /**
     * 等距取点，目的是消除密集或重复的点
     *
     * @param coordinatePointList 坐标点列
     * @return 等距点列
     */
    public static List<Point> equidistantPoint(List<Point> coordinatePointList, double distance) {
        List<Point> equidistantPointList = new LinkedList<>();

        int currentIndex = 0;
        int index = 0;

        while (true) {
            Point currentPoint = coordinatePointList.get(currentIndex);
            currentPoint.setEquIndex(index++);
            equidistantPointList.add(currentPoint);

            int nextIndex = getNextPointIndexByDistance(coordinatePointList, distance, currentIndex);
            if (nextIndex == currentIndex || nextIndex == coordinatePointList.size() - 1) {
                break;
            }
            currentIndex = nextIndex;
        }

        return equidistantPointList;
    }

    /**
     * 给定等距点列，开始索引和结束索引，连接开始点和结束点，得到一条线段L，
     * 等距点列中的从开始索引到结束索引之间的所有点当中，计算出距离线段L的最大距离的点及其索引
     *
     * @param coordinatePointList 等距点列
     * @param beginIndex          开始索引
     * @param endIndex            结束索引
     * @return 最大距离的点和最大距离
     */
    private static Object[] calcMaxDistance(List<Point> coordinatePointList, int beginIndex, int endIndex) {
        Object[] result = new Object[2];

        if (endIndex - beginIndex <= 1) {
            result[0] = beginIndex;
            result[1] = 0;
            return result;
        }

        double maxDistance = -1;
        int index = beginIndex;

        for (int i = beginIndex + 1; i < endIndex; i++) {
            Point p1 = coordinatePointList.get(beginIndex);
            Point p2 = coordinatePointList.get(endIndex);
            Point pi = coordinatePointList.get(i);

            double distance = GeometryAlgorithms.minDistance2LineOrLineSegment(p1, p2, pi, true);
            if (distance > maxDistance) {
                maxDistance = distance;
                index = i;
            }
        }

        result[0] = index;
        result[1] = maxDistance;

        return result;
    }

    /**
     * 计算权重，递归算法，Douglas-Peucker算法的环节，点的权重越大，表示越可能是拐点
     * 这个算法的权重其实是距离
     *
     * @param coordinatePointList 等距点列
     * @param result              权重列表
     * @param beginIndex          开始索引
     * @param endIndex            结束索引
     */
    private static void calcWeight(List<Point> coordinatePointList, Map<Integer, Double> result, int beginIndex, int endIndex) {
        if (endIndex - beginIndex <= 1) return;
        Object[] indexAndDistance = calcMaxDistance(coordinatePointList, beginIndex, endIndex);

        int index = (Integer) indexAndDistance[0];
        double dis = (Double) indexAndDistance[1];

        result.put(index, dis);

        calcWeight(coordinatePointList, result, beginIndex, index);
        calcWeight(coordinatePointList, result, index, endIndex);
    }

    /**
     * 计算权重，封装了计算权重递归算法，得到的权重是每一个点的距离除以最大距离
     *
     * @param coordinatePointList 等距点列
     * @return 索引与权重的映射
     */
    public static Map<Integer, Double> calcWeight(List<Point> coordinatePointList) {
        Map<Integer, Double> weight = new HashMap<>();
        calcWeight(coordinatePointList, weight, 0, coordinatePointList.size() - 1);

        final double[] maxWeight = {-1};
        weight.forEach((i, d) -> {
            if (d > maxWeight[0]) {
                maxWeight[0] = d;
            }
        });

        weight.forEach((i, d) -> weight.replace(i, d / maxWeight[0]));

        return weight;
    }

    /**
     * 将权重小于阀值的值去掉，保留首尾
     *
     * @param weight    索引权重映射
     * @param maxWeight 阀值
     * @return 过滤后点列索引列表
     */
    private static List<Integer> filterWeight(Map<Integer, Double> weight, double maxWeight) {
        List<Integer> result = new LinkedList<>();
        result.add(0);

        weight.forEach((i, d) -> {
            if (d > maxWeight) result.add(i);
        });

        if (!result.contains(weight.size() + 1)) {
            result.add(weight.size() + 1);
        }

        Collections.sort(result);

        return result;
    }

    /**
     * Douglas-Peucker算法，保留首尾
     *
     * @param coordinatePointList 等距点列
     * @param maxWeight           最大权重
     * @return 拐点索引
     */
    private static List<Integer> douglasPeucker(List<Point> coordinatePointList, double maxWeight) {
        return filterWeight(calcWeight(coordinatePointList), maxWeight);
    }

    /**
     * Douglas-Peucker算法，保留首尾
     *
     * @param coordinatePointList 等距点列
     * @param maxWeight           最大权重
     * @return 拐点
     */
    private static List<Point> douglasPeuckerPoint(List<Point> coordinatePointList, double maxWeight) {
        return PolygonAlgorithms.createPolygonInclude(coordinatePointList, douglasPeucker(coordinatePointList, maxWeight));
    }

    /**
     * 循环Douglas-Peucker算法，目的是去掉首尾
     *
     * @param coordinatePointList 等距点列
     * @param maxWeight           最大权重
     * @return 拐点
     */
    private static LinkedList<Point> douglasPeuckerCyc(List<Point> coordinatePointList, double maxWeight) {
        LinkedList<Point> oldList = (LinkedList<Point>) coordinatePointList;
        LinkedList<Point> newList;

        while (true) {
            newList = (LinkedList<Point>) douglasPeuckerPoint(oldList, maxWeight);

            if (newList.size() == oldList.size()) {
                break;
            }

            newList.add(newList.pop());
            oldList = newList;
        }

        Collections.sort(newList);

        return newList;
    }

    /**
     * 两个拐点之间的散点用直线拟合（首尾相接），并返回新的顶点，顶点是相邻的拟合直线的交点
     *
     * @param coordinatePointList 等距点列
     * @param turnPointIndexList  有序拐点索引列表
     * @return 新的顶点
     */
    public static List<Point> fit(List<Point> coordinatePointList, List<Integer> turnPointIndexList) {
        int turnPointIndexListSize = turnPointIndexList.size();
        int coordinatePointListSize = coordinatePointList.size();
        double[][] bks = new double[turnPointIndexListSize][2];
        for (int i = 0; i < turnPointIndexListSize; i++) {
            int beginIndex = turnPointIndexList.get(i);
            int endIndex = turnPointIndexList.get((i + 1) % turnPointIndexListSize);
            double[][] data;
            int dataLength = endIndex - beginIndex;
            if (dataLength < 0) {
                dataLength = coordinatePointListSize + dataLength + 1;
                data = new double[dataLength][2];
                for (int j = beginIndex; j < coordinatePointListSize; j++) {
                    data[j - beginIndex] = coordinatePointList.get(j).getData();
                }
                int delta = coordinatePointListSize - beginIndex;
                for (int j = 0; j < endIndex; j++) {
                    data[j + delta] = coordinatePointList.get(j).getData();
                }
            } else {
                dataLength++;
                data = new double[dataLength][2];
                for (int j = beginIndex; j <= endIndex; j++) {
                    data[j - beginIndex] = coordinatePointList.get(j).getData();
                }
            }
            bks[i] = GeometryAlgorithms.linearFit(data);
        }
        List<Point> result = new LinkedList<>();
        for (int i = 0; i < turnPointIndexListSize; i++) {
            result.add(new Point(GeometryAlgorithms.getIntersectPointByTwoLines(bks[i], bks[(i + 1) % turnPointIndexListSize])));
        }
        return result;
    }

    /**
     * 得到拐点，拟合点，和外扩点
     *
     * @param oriTrace         原始点列
     * @param extendDistance   外扩距离
     * @param distanceTwoPoint 相邻两点之间的距离
     * @param maxWeight        最大权重
     * @return 拐点，拟合点，外扩点
     */
    public static TurnFitExtendResult turnFitExtend(List<Point> oriTrace, double extendDistance, double distanceTwoPoint, double maxWeight) {
        List<Point> coorTrace = GPSAlgorithms.gps2Coor(oriTrace, oriTrace.get(0));
        List<Point> equidistantPointList = TurnFitExtendAlgorithms.equidistantPoint(coorTrace, distanceTwoPoint);
        LinkedList<Point> turnPointList = douglasPeuckerCyc(equidistantPointList, maxWeight);
        List<Integer> equIndexesFromTurnPointList = PolygonAlgorithms.getEquIndexesFromPointList(turnPointList);
        List<Point> fitPointList = fit(equidistantPointList, equIndexesFromTurnPointList);
        List<Point> extendPointList = PolygonAlgorithms.extendPolygon(fitPointList, extendDistance);
        fitPointList = GPSAlgorithms.coor2Gps(fitPointList, oriTrace.get(0));
        extendPointList = GPSAlgorithms.coor2Gps(extendPointList, oriTrace.get(0));

        TurnFitExtendResult result = new TurnFitExtendResult();

        result.setTurn(PolygonAlgorithms.getOriIndexesFromPointList(turnPointList));
        result.setFit(fitPointList);
        result.setExtend(extendPointList);

        return result;
    }

}
